P3232 [HNOI2013]游走

这道题边的数量最高是10000多,而点只有500,这提醒我们,我们不能直接对边求期望,而是点。

Expection[u]Expection[u]表示点uu的期望走过次数,Degree[u]Degree[u]表示点uu的度数。

那么,

Expection[u]=vuExpection[v]Degree[v]Expection[u]=\sum_{v \in u}\frac{Expection[v]}{Degree[v]}

但是,你会发现,Expection[v]Expection[v]要依靠Expection[u]Expection[u],不能直接计算。

再次观察后,既然每一项都有其他项,类似方程形式,那我们可以用高斯消元解决,计算出每一点的ExpectionExpection

然后,我们先不考虑边权,根据点算出边的期望,当点u,vu,v之间存在一条边时,(u,v)(u,v)这条边显然只与点u,vu,v有关,且该边的期望为:

Expection(u,v)=Expection[u]Degree[u]+Expection[v]Degre[v]Expection(u,v)=\frac{Expection[u]}{Degree[u]}+\frac{Expection[v]}{Degre[v]}

之后,利用贪心的思想,期望经过值越大,我们就分配越小的权值,统计一下答案就好了。

注意:边数可达点数平方/2,跟边有关的数组开 MAXN\text{MAXN} 的平方。

// luogu-judger-enable-o2
#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-10

const int MAXN = 500;
int n , m , u , v , Degree[ MAXN + 5 ] , S[ MAXN * MAXN ] , T[ MAXN * MAXN ];
double a[ MAXN + 5 ][ MAXN + 5 ] , Expection[ MAXN * MAXN + 5 ]; //a数组为点i到点n,点i的期望走过次数
vector< int > Graph[ MAXN + 5 ];

void Gauss( ) {
    int Row , Column;
    for( int i = 1 ; i < n ; i ++ ) {
        Column = i;
        for( int j = i ; j <= n ; j ++ )
            if( fabs( a[ j ][ i ] ) > fabs( a[ Column ][ i ] ) )
                Column = j;
        swap( a[ i ] , a[ Column ] );
        for( int j = n ; j >= i ; j -- ) 
        	a[ i ][ j ] /= a[ i ][ i ];
        for( int j = 1 ; j < n ; j ++ )
            if( i != j )
				for( int k = n ; k >= i ; k -- )
                	a[ j ][ k ] -= a[ j ][ i ] * a[ i ][ k ];
    }
}

int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d",&u,&v);
        Degree[ u ] ++ , Degree[ v ] ++;
        Graph[ u ].push_back( v );
        Graph[ v ].push_back( u );
        S[ i ] = u , T[ i ] = v;
    }
    a[ 1 ][ n ] = 1;
    for( int i = 1 ; i < n ; i ++ )  {
        a[ i ][ i ] = 1;
        for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
            int v = Graph[ i ][ j ];
            if( v != n ) a[ i ][ v ] = -1.0 / Degree[ v ];
        }
    }
    Gauss( );

    for( int i = 1 ; i <= m ; i ++ ) {
        if( S[ i ] != n )
            Expection[ i ] += a[ S[ i ] ][ n ] * ( 1.0 / Degree[ S[ i ] ] );
        if( T[ i ] != n )
            Expection[ i ] += a[ T[ i ] ][ n ] * ( 1.0 / Degree[ T[ i ] ] );
    }
    sort( Expection + 1 , Expection + m + 1 );

    double Ans = 0;
    for( int i = 1 ; i <= m ; i ++ )
        Ans += Expection[ i ] * 1.0 * ( m - i + 1 );
    printf("%.3lf",Ans);
    return 0;
}